Thẩm Dị Cơ vốn là người đất Bái, cùng quê với Lưu Bang.

Năm 205 TCN, Lưu Bang nhân lúc Hạng Vũ sa lầy chiến tranh ở nước Tề, bèn cùng các chư hầu tiến vào đánh chiếm kinh đô Tây Sở là Bành Thành. Do chủ quan, Lưu Bang bị Hạng Vũ mang quân về đánh cho đại bại. Lưu Bang vội vã bỏ chạy. Cha và vợ Lưu Bang là Lưu Thái Công và Lã Trĩ bị quân Tây Sở bắt được. Lúc đó Thẩm Dị Cơ cùng bị bắt với Lưu Công và Lã Trĩ, theo hầu hạ Lã Trĩ ở đất Tây Sở[2].

Sau 2 năm, năm 203 TCN, Lưu Bang và Hạng Vũ giảng hòa, Hạng Vũ bèn tha cho Lưu Công và Lã Trĩ về với Hán vương Lưu Bang. Thẩm Dị Cơ cũng trở về Hán. Ông được Hán vương cất nhắc làm Tịch Dương hầu và được Lã Trĩ yêu[2].